package com.bubaiwantong.algorithms.insert;

/**
 * @author bubaiwantong
 * @description
 */
public class InsertSort {

    /**
     * 插入排序之简单插入排序
     *
     * @param args
     */

    public static void main(String[] args) {
        int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        InsertSort insertSort = new InsertSort();
        insertSort.print(arr);
        insertSort.sort(arr);
        insertSort.print(arr);
    }

    /**
     * 简单插入排序算法
     * 算法伪代码：
     * 1、计数器变量i从1开始，到n结束。
     * 1.1、j从i-1开始，到0结束，选择在（0~i）范围内寻找到（i+1）号元素合适的位置，
     * 1.2、找到的位置命名为position，并将这两个元素的值进行交换
     *
     * @param arr
     */
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while (j > 0) {
                if (arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                    j--;
                }
            }
            arr[j] = temp;
        }
    }


    /**
     * 将数组中的两个元素进行交换
     *
     * @param arr
     * @param i
     * @param j
     */
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
